"""
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"
"""
import pprint

class Solution:
    """
    循环出所有的可能性，判断是不是回文
    结果：完美超时
    """
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        n = len(s)
        dp = [[0]* n for i in range(n)]
        # 初始化长度为1的
        for i in range(n):
            dp[i][i] = 1
        
        def is_palindrome(string: str):
            return string == string[::-1]
        max_palindrome = s[0]
        # 初始化长度为2的
        for i in range(n-1):
            if is_palindrome(s[i:i+2]):
                dp[i][i+1] = 1
                max_palindrome = s[i:i+2]
        
        for i in range(3, n+1):
            for j in range(0, n-i+1):
                if dp[j+1][j+i-2] and s[j] == s[j+i-1]:
                    # print(j ,j+i, s[j:j+i])
                    if len(max_palindrome) < i: # 如果长度小与现在这个回文的长度，就重新赋值
                        max_palindrome = s[j:j+i]
                    dp[j][j+i-1] = 1
                
        return max_palindrome


if __name__ == "__main__":
    print(Solution().longestPalindrome("b"))